#include <iostream>
#include <vector>

using namespace std;

// 98.验证二叉搜索树
// 给定一棵二叉树，验证其是否为二分搜索树。
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(): val(0),left(nullptr),right(nullptr) {}
    TreeNode(int x): val(x),left(nullptr),right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
// 中序遍历，判断是否为有序
class Solution {
public:
    bool isValidBST(TreeNode *root) {
        if(root == nullptr || (root->left == nullptr && root->right == nullptr))
            return true;
        vector<int> vec;
        inorderTree(root, vec);
        // 判断是否有序
        for(int i = 0; i < vec.size() - 1; i++)
            if(vec[i] >= vec[i+1])
                return false;
        return true;
    }
private:
    void inorderTree(TreeNode *node, vector<int>& vec) {
        if(node == nullptr)
            return;
        inorderTree(node->left, vec);
        vec.push_back(node->val);
        inorderTree(node->right, vec);
    }
};

int main() {
    TreeNode* root = new TreeNode(2);

    TreeNode* left = new TreeNode(1);
    root->left = left;

    TreeNode* right = new TreeNode(3);
    root->right = right;
    //==============================
    auto *root2 = new TreeNode(5, new TreeNode(1),
                               new TreeNode(4,
                                            new TreeNode(3),
                                            new TreeNode(6)
                                            )
                                            );
    TreeNode* root3 = new TreeNode(2, new TreeNode(2), new TreeNode(2));


//    cout << Solution().isValidBST(root) << endl;
//    cout << Solution().isValidBST(root2) << endl;
    cout << Solution().isValidBST(root3) << endl;
    return 0;
}
